package likou;

import java.util.Arrays;

/**
 * @author: Tangxz
 * @email: 1171702529@qq.com
 * @cate: 2020/11/11 07:08
 */
public class _514 {
    public static void main(String[] args) {
        System.out.println(findRotateSteps("godding", "gd"));
    }

    public static int findRotateSteps(String ring, String key) {
        final int n = ring.length();
        final int[] memo = new int[n];//存储每一个位置的最优解
        final int[] count = new int[26];
        final char[] cs = ring.toCharArray();
        for (char c : cs) {
            count[c - 'a']++;
        }
        final int[][] positions = new int[26][];
        for (int i = 0; i < 26; i++) {
            positions[i] = new int[count[i]];
        }
        Arrays.fill(count, 0);
        for (int i = 0; i < n; i++) {
            positions[cs[i] - 'a'][count[cs[i] - 'a']++] = i;
        }
        for (int idx : positions[key.charAt(0) - 'a']) {
            memo[idx] = 1 + distance(0, idx, n);
        }
        for (int idx = 1; idx != key.length(); idx++) {
            int il = key.charAt(idx - 1) - 'a', ic = key.charAt(idx) - 'a';
            int[] cur = positions[ic];
            if (il == ic) {
                for (int i : cur) {
                    memo[i]++;
                }
                continue; // special ops. should be right
            }
            int[] last = positions[il];
            for (int i : cur) {
                int midDistance = Integer.MAX_VALUE; // note. cannot n
                for (int j : last) {
                    midDistance = Math.min(midDistance, memo[j] + distance(i, j, n));
                }
                memo[i] = midDistance + 1;
            }
        }
        int res = Integer.MAX_VALUE; // note cannot n
        for (int idx : positions[key.charAt(key.length() - 1) - 'a']) {
            res = Math.min(res, memo[idx]);
        }
        return res;
    }

    /**
     * @param src
     * @param dest
     * @param n
     * @return 返回到某个下标的最短路径值
     */
    private static int distance(int src, int dest, final int n) {
        if (src < dest) {
            return Math.min(dest - src, n - dest + src);
        } else {
            return Math.min(src - dest, n - src + dest);
        }
    }
}
